Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Missing Ranges

Problem Statement

You are given two integers, lower and upper, specifying the inclusive range, and the sorted array of unique integers nums, where each element is in between [lower, upper].

We can say the number n is missing if n is not in the nums and falls in the range [lower, upper].

Return the shortest sorted list of ranges that covers all missing numbers. These ranges should fall within the inclusive bounds specified by the lower and upper limit integers.

Examples

Example 1:

  • Input: nums = [3, 5, 10, 20], lower = 1, upper = 22
  • Expected Output: [[1, 2], [4, 4], [6, 9], [11, 19], [21, 22]]
  • Justification: The missing ranges are 1-2, 4, 6-9, 11-19, and 21-22. Each missing range is represented as a pair in the list, where both numbers are the same for a single missing number.

Example 2:

  • Input: nums = [10, 20, 30, 40, 50], lower = 5, upper = 55
  • Expected Output: [[5, 9], [11, 19], [21, 29], [31, 39], [41, 49], [51, 55]]
  • Justification: The missing ranges are 5-9, 11-19, 21-29, 31-39, 41-49, and 51-55. Each interval is represented as a pair of start and end values.

Example 3:

  • Input: nums = [1, 3, 6, 10], lower = 0, upper = 12
  • Expected Output: [[0, 0], [2, 2], [4, 5], [7, 9], [11, 12]]
  • Justification: The missing ranges are 0, 2, 4-5, 7-9, and 11-12. Each range is represented as a start and end pair.

Solution

To solve this problem, the primary approach involves iterating through the list and identifying gaps between consecutive elements compared to the given lower and upper bounds. The solution must account for ranges at the beginning and end of the list that might not be covered by the elements.

This approach works effectively because it systematically checks each interval between the numbers in the sorted list against the specified bounds. By comparing adjacent numbers and the bounds, we can easily identify the missing ranges. The algorithm is simple and efficient for a sorted list, as it requires only a single pass through the list.

Step-by-step Algorithm

  • Initialize an empty list result to store the missing ranges.
  • Add the range from lower to the first element in the list (if needed).
  • Iterate through the list of numbers:
    • For each pair of adjacent numbers, check if there is a gap (difference > 1).
    • If a gap exists, add the missing range to result.
  • After the loop, add the range from the last element to upper (if needed).
  • Return the result list containing all the missing ranges.

Algorithm Walkthrough

Let's use Example 1 for the walkthrough:

  • Input: nums = [3, 5, 10, 20], lower = 1, upper = 22
  • Steps:
    1. Initialize result as an empty list.
    2. The first number (3) does not match lower (1), so we add the range [1, 2].
    3. Check gaps:
      • Between 3 and 5, gap exists (4), add [4, 4].
      • Between 5 and 10, gap exists (6-9), add [6, 9].
      • Between 10 and 20, gap exists (11-19), add [11, 19].
    4. After the loop, add the range from the last number (20) to upper (22), i.e., [21, 22].
    5. The final result is [[1, 2], [4, 4], [6, 9], [11, 19], [21, 22]].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity: ( O(N) )

The algorithm iterates through the given list of ( N ) elements once. Each iteration involves constant-time operations. Therefore, the overall time complexity is linear, ( O(N) ).

Space Complexity: ( O(M) )

The space complexity is determined by the number of missing ranges stored in the result list. In the worst case, this could be proportional to the difference between upper and lower bounds. If ( M ) represents the number of missing ranges, the space complexity is ( O(M) ).

Missing Ranges (easy)
Palindrome Permutation (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity: ( O(N) )

Space Complexity: ( O(M) )